Cos'è selection sort?

Selection Sort (Ordinamento per Selezione)

L'Selection Sort è un semplice algoritmo di ordinamento in loco. È inefficiente su grandi liste, e generalmente performa peggio di algoritmi simili come l' Insertion Sort.

Come funziona:

1. Trova l'elemento minimo nella lista non ordinata.
2. Scambia questo elemento con il primo elemento della lista non ordinata.
3. Ripeti i passaggi 1 e 2 per la rimanente parte non ordinata della lista.

In sostanza, l'algoritmo divide la lista in due parti: una sottolista già ordinata, costruita dall'inizio della lista a sinistra, e una sottolista rimanente non ordinata, che occupa il resto della lista. Ad ogni iterazione, l'elemento minimo della sottolista non ordinata viene selezionato e spostato alla fine della sottolista ordinata.

Caratteristiche:

• Semplicità: Facile da capire e implementare.
• In-place: Richiede solo una quantità costante di memoria extra. Non necessita di ulteriore spazio in memoria proporzionale alla dimensione dell'input, rendendolo efficiente in termini di memoria.
• Instabile: Non preserva l'ordine relativo di elementi con lo stesso valore. Ad esempio, se hai due elementi con il valore 5, l'ordine relativo potrebbe cambiare dopo l'ordinamento. (Per ulteriori informazioni, vedi stabilità.)

Complessità temporale:

• Caso migliore: O(n²)
• Caso medio: O(n²)
• Caso peggiore: O(n²)

Complessità spaziale: O(1)

La complessità temporale di O(n²) lo rende inefficiente per grandi dataset. Anche se l'Insertion Sort ha la stessa complessità temporale, in pratica performa meglio di Selection Sort. L'Selection Sort ha il vantaggio di effettuare un numero minimo di scambi: al massimo n-1, dove n è la lunghezza della lista. Questo lo rende utile in situazioni dove il costo degli scambi è elevato.

Quando usarlo:

• Quando la dimensione del dataset è piccola.
• Quando gli scambi sono costosi e il numero di scritture in memoria deve essere minimizzato. In sostanza, se leggere è economico e scrivere è costoso, allora potrebbe essere una buona scelta.
• Come strumento didattico per introdurre i concetti di algoritmi di ordinamento.